package com.sheng.leetcode.year2023.month07.day18;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author liusheng
 * @date 2023/07/18
 * <p>
 * 1851. 包含每个查询的最小区间<p>
 * <p>
 * 给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、<p>
 * 结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。<p>
 * 再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的<p>
 * 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。<p>
 * 以数组形式返回对应查询的所有答案。<p>
 * <p>
 * 示例 1：<p>
 * 输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]<p>
 * 输出：[3,3,1,4]<p>
 * 解释：查询处理如下：<p>
 * - Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。<p>
 * - Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。<p>
 * - Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。<p>
 * - Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]<p>
 * 输出：[2,-1,4,6]<p>
 * 解释：查询处理如下：<p>
 * - Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。<p>
 * - Query = 19：不存在包含 19 的区间，答案为 -1 。<p>
 * - Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。<p>
 * - Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。<p>
 * <p>
 * 提示：<p>
 * 1 <= intervals.length <= 10^5<p>
 * 1 <= queries.length <= 10^5<p>
 * queries[i].length == 2<p>
 * 1 <= lefti <= righti <= 10^7<p>
 * 1 <= queries[j] <= 10^7<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-interval-to-include-each-query">1851. 包含每个查询的最小区间</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1851 {

    @Test
    public void test01() {
//        int[][] intervals = {{1, 4}, {2, 4}, {3, 6}, {4, 4}};
//        int[] queries = {2, 3, 4, 5};
        int[][] intervals = {{2, 3}, {2, 5}, {1, 8}, {20, 25}};
        int[] queries = {2, 19, 5, 22};
        System.out.println(Arrays.toString(new Solution().minInterval(intervals, queries)));
    }
}

// 超时
//class Solution {
//    public int[] minInterval(int[][] intervals, int[] queries) {
//        int n = queries.length;
//        int[] ans = new int[n];
//        Arrays.fill(ans, -1);
//        for (int i = 0; i < queries.length; i++) {
//            for (int[] interval : intervals) {
//                if (interval[0] <= queries[i] && interval[1] >= queries[i]) {
//                    if (ans[i] == -1) {
//                        ans[i] = interval[1] - interval[0] + 1;
//                    } else {
//                        ans[i] = Math.min(ans[i], interval[1] - interval[0] + 1);
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//}
class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int n = intervals.length, m = queries.length;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int[][] qs = new int[m][0];
        for (int i = 0; i < m; ++i) {
            qs[i] = new int[]{queries[i], i};
        }
        Arrays.sort(qs, Comparator.comparingInt(a -> a[0]));
        int[] ans = new int[m];
        Arrays.fill(ans, -1);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int i = 0;
        for (int[] q : qs) {
            while (i < n && intervals[i][0] <= q[0]) {
                int a = intervals[i][0], b = intervals[i][1];
                pq.offer(new int[]{b - a + 1, b});
                ++i;
            }
            while (!pq.isEmpty() && pq.peek()[1] < q[0]) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                ans[q[1]] = pq.peek()[0];
            }
        }
        return ans;
    }
}
